CoCalc Logo Icon
DocsShareSupport News Sign UpSign In
Views: 87
Image: ubuntu2004
Embed | Download | Raw |
Kernel: Python 3 (ipykernel)
import random from IPython.core.display import SVG import pyomo.environ as pyo from pysat.solvers import Solver from pysat.formula import CNF import py_svg_combinatorics as psc from ipywidgets import widgets, HBox from collections import Counter from pprint import pprint from random import randint import numpy as np from IPython.display import IFrame import IPython from copy import copy import os from pathlib import Path np.set_printoptions(precision=2) np.set_printoptions(suppress=True) nbname = '' try: nbname = __vsc_ipynb_file__ except: if 'COCALC_JUPYTER_FILENAME' in os.environ: nbname = os.environ['COCALC_JUPYTER_FILENAME'] title_ = Path(nbname).stem.replace('-', '_').title() IFrame(f'https://discopal.ispras.ru/index.php?title=Hardprob/{title_}&useskin=cleanmonobook', width=1280, height=300)
# Случайные данные m = np.random.randint(3, 20) n = np.random.randint(3, 20) A = np.random.rand(m, n) c = np.random.rand(n) b = 1/np.random.rand(m) # Модифицируем тестовые данные, чтобы получались только задачи имеющие решение. for i in range(len(b)): b[i] = min(b[i], sum(A[i, j] for j in range(n))) A, b, c
(array([[0.37, 0.94, 0.72, 0.96, 0.34, 0.21, 0.84, 0.95, 0.83, 0.73, 0.96, 0.13, 0.81, 0.05, 0.44, 0.41, 0.28, 0.45, 0.9 ], [0.48, 0.38, 0.66, 0.97, 0.74, 0.93, 0.76, 0.29, 0.3 , 0.18, 0.34, 0.39, 0.61, 0.9 , 0.23, 0.11, 0.41, 0.78, 0.41], [0.01, 0.61, 0.66, 0.55, 0.84, 0.71, 0.95, 0.17, 0.13, 0.74, 0.79, 0.82, 0.7 , 0.89, 0.52, 0.76, 0.89, 0.13, 0.49], [0.87, 0.72, 0.17, 0.4 , 0.07, 0.78, 0.03, 0.08, 0.78, 0.84, 0.61, 0.63, 0.37, 0.54, 0.81, 0.18, 0.9 , 0.13, 0.67], [0.94, 0.18, 0.06, 0.11, 0.64, 0.68, 0.37, 0.16, 0.1 , 0.52, 0.45, 0.44, 0.34, 0.84, 0.3 , 0.92, 0.94, 0.5 , 0.08], [0. , 0.12, 0.44, 0.8 , 1. , 0.2 , 0.78, 0.13, 0.79, 0.17, 1. , 0.83, 0.97, 0.27, 0.14, 0.79, 0.63, 0.26, 0.36], [0.95, 0.79, 0.12, 0.72, 0.21, 0.39, 0.94, 0.17, 0.4 , 0.12, 0.82, 0.01, 0.23, 0.56, 0.46, 0.99, 0.22, 0.71, 0.59], [0.68, 0.49, 0.65, 0.59, 0.85, 0.05, 0.56, 0.94, 0.05, 0.75, 0.43, 0.3 , 0.39, 0.36, 0.7 , 0.13, 0.42, 0.49, 0.66], [0.48, 0.75, 0.67, 0.92, 0.63, 0.72, 0.21, 0.7 , 0.17, 0.05, 0.52, 0.55, 0.62, 0.22, 0.29, 0.73, 0.5 , 0.32, 0.83], [0.73, 0.57, 0.41, 0.5 , 0.34, 0. , 0.14, 0.28, 0.74, 0.75, 0.92, 0.17, 0.48, 0.21, 0.87, 0.2 , 0.72, 0.91, 0.87], [0.11, 0.06, 0.64, 0.37, 0.9 , 0.32, 0.87, 0.51, 0.11, 0.29, 0.77, 0.66, 0.01, 0.39, 0.13, 0.1 , 0.48, 0.4 , 0.5 ], [0.78, 0.08, 0.17, 0.5 , 0.66, 0.42, 0.9 , 0.13, 0.27, 0.92, 0.99, 0.26, 0.2 , 0.37, 0.64, 0.14, 0.4 , 0.11, 0.47]]), array([3.19, 1.32, 1.32, 1.16, 2.33, 1.02, 4.02, 1.17, 1.81, 1.01, 1.6 , 7. ]), array([0.37, 0.76, 0.12, 0.09, 0.73, 0.82, 0.61, 0.69, 0.97, 0.22, 0.35, 0.77, 0.13, 0.04, 0.66, 0.19, 0.84, 0.25, 0.37]))

def get_model(A, b, c): m = pyo.ConcreteModel() m.m, m.n = A.shape # на всякий случай, возьмем с собой m.A = A m.b = b m.c = c m.I = range(m.m) m.J = range(m.n) m.x = pyo.Var(m.J, domain=pyo.Binary) m.obj = pyo.Objective(expr = sum( c[j] * m.x[j] for j in m.J), sense=pyo.minimize) @m.Constraint(m.I) def не_меньше(m, i): return sum(A[i, j] * m.x[j] for j in m.J) >= b[i] return m m = get_model(A, b, c) m.pprint()
2 Set Declarations x_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 19 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18} не_меньше_index : Size=1, Index=None, Ordered=Insertion Key : Dimen : Domain : Size : Members None : 1 : Any : 12 : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} 1 Var Declarations x : Size=19, Index=x_index Key : Lower : Value : Upper : Fixed : Stale : Domain 0 : 0 : None : 1 : False : True : Binary 1 : 0 : None : 1 : False : True : Binary 2 : 0 : None : 1 : False : True : Binary 3 : 0 : None : 1 : False : True : Binary 4 : 0 : None : 1 : False : True : Binary 5 : 0 : None : 1 : False : True : Binary 6 : 0 : None : 1 : False : True : Binary 7 : 0 : None : 1 : False : True : Binary 8 : 0 : None : 1 : False : True : Binary 9 : 0 : None : 1 : False : True : Binary 10 : 0 : None : 1 : False : True : Binary 11 : 0 : None : 1 : False : True : Binary 12 : 0 : None : 1 : False : True : Binary 13 : 0 : None : 1 : False : True : Binary 14 : 0 : None : 1 : False : True : Binary 15 : 0 : None : 1 : False : True : Binary 16 : 0 : None : 1 : False : True : Binary 17 : 0 : None : 1 : False : True : Binary 18 : 0 : None : 1 : False : True : Binary 1 Objective Declarations obj : Size=1, Index=None, Active=True Key : Active : Sense : Expression None : True : minimize : 0.3658961836940545*x[0] + 0.758277550891349*x[1] + 0.1152126825966977*x[2] + 0.08848485037028375*x[3] + 0.7269526082434031*x[4] + 0.8239761738588355*x[5] + 0.6144609798330439*x[6] + 0.6876160245293927*x[7] + 0.9665154187468914*x[8] + 0.22493435340756984*x[9] + 0.3463932547841474*x[10] + 0.7693442194529974*x[11] + 0.12857378891150362*x[12] + 0.04011718202352377*x[13] + 0.6580774827137869*x[14] + 0.19131504418992196*x[15] + 0.8414168272287447*x[16] + 0.24637468513374838*x[17] + 0.36840492688528237*x[18] 1 Constraint Declarations не_меньше : Size=12, Index=не_меньше_index, Active=True Key : Lower : Body : Upper : Active 0 : 3.186432185169367 : 0.37144875910866115*x[0] + 0.9351854212243987*x[1] + 0.7153836057557165*x[2] + 0.9618540590388255*x[3] + 0.3391824816169464*x[4] + 0.20554009769279702*x[5] + 0.8395795478519278*x[6] + 0.9475934651312397*x[7] + 0.8254724322212118*x[8] + 0.7282143747730794*x[9] + 0.956938667597803*x[10] + 0.1288791162038767*x[11] + 0.8085148862974832*x[12] + 0.05006437448774925*x[13] + 0.44441216988950905*x[14] + 0.4063978259334149*x[15] + 0.281566101773024*x[16] + 0.4527173492238564*x[17] + 0.8954730406290029*x[18] : +Inf : True 1 : 1.3216033371576599 : 0.47726931405591133*x[0] + 0.38164981032531375*x[1] + 0.6554000350252811*x[2] + 0.9746915763920871*x[3] + 0.7421705663777812*x[4] + 0.9267261496846826*x[5] + 0.7634170297890299*x[6] + 0.29006678683666953*x[7] + 0.299229646816635*x[8] + 0.1845757885552306*x[9] + 0.3400298645121712*x[10] + 0.39047506119960074*x[11] + 0.61137405096717*x[12] + 0.8998235500241688*x[13] + 0.23271964325495798*x[14] + 0.1116609030272091*x[15] + 0.41306742507634653*x[16] + 0.7834866819218336*x[17] + 0.4065431611222642*x[18] : +Inf : True 2 : 1.318260892254717 : 0.010599347246679658*x[0] + 0.6114485803659613*x[1] + 0.6594272397122483*x[2] + 0.5475476987927693*x[3] + 0.8363306209825118*x[4] + 0.7122428572632001*x[5] + 0.9482359695592589*x[6] + 0.1673057020077845*x[7] + 0.13385842927626435*x[8] + 0.7363475167226983*x[9] + 0.7944292723170207*x[10] + 0.819892098377287*x[11] + 0.70217417832277*x[12] + 0.8926014055007739*x[13] + 0.5175344930635557*x[14] + 0.7628363893433403*x[15] + 0.8896582793415634*x[16] + 0.12676475244557617*x[17] + 0.48638664088448913*x[18] : +Inf : True 3 : 1.160082157541207 : 0.8696358378869057*x[0] + 0.7186218385401603*x[1] + 0.1664426200430399*x[2] + 0.4026536125775839*x[3] + 0.07193911709344902*x[4] + 0.7791775796328917*x[5] + 0.03171420765571842*x[6] + 0.07989998845730117*x[7] + 0.775734454233105*x[8] + 0.8352765347425188*x[9] + 0.613247867441524*x[10] + 0.6344512576025951*x[11] + 0.37391344001303783*x[12] + 0.5421486386015916*x[13] + 0.8134430493664881*x[14] + 0.1810411537371085*x[15] + 0.9027649944081441*x[16] + 0.130579169593105*x[17] + 0.6694083165069147*x[18] : +Inf : True 4 : 2.3299384420313562 : 0.9363917999677521*x[0] + 0.18343923694156128*x[1] + 0.055652397792570696*x[2] + 0.1109251190111723*x[3] + 0.6401446011637942*x[4] + 0.6836692937848166*x[5] + 0.37160555915284454*x[6] + 0.1578572627672834*x[7] + 0.09825935949672693*x[8] + 0.5188120577742371*x[9] + 0.4546805232398944*x[10] + 0.44235784719261817*x[11] + 0.3429817766789175*x[12] + 0.8367798602819253*x[13] + 0.3045171223644356*x[14] + 0.9173828457367951*x[15] + 0.9416964520271649*x[16] + 0.5030524634219686*x[17] + 0.08155793010829815*x[18] : +Inf : True 5 : 1.023791018826223 : 0.0004318695187512933*x[0] + 0.11539813615436201*x[1] + 0.4366769335993774*x[2] + 0.8004286003879542*x[3] + 0.9980702662517652*x[4] + 0.1950320763021951*x[5] + 0.7750978954597821*x[6] + 0.13405163480501292*x[7] + 0.7939386987559719*x[8] + 0.17255598796473748*x[9] + 0.9984413110832068*x[10] + 0.8306404101803364*x[11] + 0.96916461588205*x[12] + 0.2707174163867918*x[13] + 0.1424371454557719*x[14] + 0.7885135198288553*x[15] + 0.6301142788807759*x[16] + 0.2561127657942377*x[17] + 0.35903268026034996*x[18] : +Inf : True 6 : 4.0195521544468 : 0.9483173487518699*x[0] + 0.7877477749169773*x[1] + 0.11683313391014416*x[2] + 0.7181438842332265*x[3] + 0.2081625925351971*x[4] + 0.38971271514731287*x[5] + 0.9434602234221016*x[6] + 0.17238052566281892*x[7] + 0.4018496009106244*x[8] + 0.1249656282161602*x[9] + 0.8174693996695686*x[10] + 0.006099844614797956*x[11] + 0.23277825401717167*x[12] + 0.5565058146210217*x[13] + 0.45568184195770967*x[14] + 0.9857101728753532*x[15] + 0.2187836450118994*x[16] + 0.7138695722431194*x[17] + 0.5908180940869869*x[18] : +Inf : True 7 : 1.1687769263758674 : 0.6796232916468007*x[0] + 0.48831112735129456*x[1] + 0.6506163086475987*x[2] + 0.592968701228239*x[3] + 0.8456754880097423*x[4] + 0.051672116361165754*x[5] + 0.5552589272897085*x[6] + 0.9360904590163706*x[7] + 0.046008138654040964*x[8] + 0.7476306389884994*x[9] + 0.4336365550303203*x[10] + 0.29996242118766303*x[11] + 0.38633224333131877*x[12] + 0.3581888577559329*x[13] + 0.7000802354919508*x[14] + 0.1305934884778689*x[15] + 0.4151690014926357*x[16] + 0.4943481864368461*x[17] + 0.6600792219131907*x[18] : +Inf : True 8 : 1.8088482994796018 : 0.4817161584823936*x[0] + 0.7491401011058471*x[1] + 0.6686458814696576*x[2] + 0.9164307310527803*x[3] + 0.6258257555946912*x[4] + 0.719392865727462*x[5] + 0.21129172280960895*x[6] + 0.7037677032337629*x[7] + 0.16682794223996533*x[8] + 0.05080938525076373*x[9] + 0.5208554525688002*x[10] + 0.5486960526543289*x[11] + 0.6171792806577029*x[12] + 0.21544847416450796*x[13] + 0.2901334672389594*x[14] + 0.7346115485663538*x[15] + 0.5046366922651645*x[16] + 0.3150766336588534*x[17] + 0.8260867574692496*x[18] : +Inf : True 9 : 1.0114887071081076 : 0.7310500036607805*x[0] + 0.570741702250223*x[1] + 0.41404097824056063*x[2] + 0.5034412027231328*x[3] + 0.34387608799778036*x[4] + 0.0005326867525700107*x[5] + 0.13513231749323373*x[6] + 0.2801496228959979*x[7] + 0.7410285909889378*x[8] + 0.7455782899588872*x[9] + 0.9218242969551245*x[10] + 0.17396609029289756*x[11] + 0.4842741477644832*x[12] + 0.21461089553083446*x[13] + 0.8685327263870858*x[14] + 0.19651971583242422*x[15] + 0.7175887375863034*x[16] + 0.9053309604232951*x[17] + 0.8708584176380839*x[18] : +Inf : True 10 : 1.6021805092467172 : 0.11225137619177028*x[0] + 0.06386792722146084*x[1] + 0.6427111766820919*x[2] + 0.37170274718401153*x[3] + 0.8972741677999425*x[4] + 0.321763168123814*x[5] + 0.8669053103199023*x[6] + 0.513427573725725*x[7] + 0.10717852996976718*x[8] + 0.2941122470009664*x[9] + 0.7738526512866206*x[10] + 0.6630416147989977*x[11] + 0.007075800483298145*x[12] + 0.38982470973566075*x[13] + 0.13230334090323292*x[14] + 0.09752482745793689*x[15] + 0.4792066413864402*x[16] + 0.4031052272258402*x[17] + 0.498610167886671*x[18] : +Inf : True 11 : 6.997036241547957 : 0.7770812171159828*x[0] + 0.08104866285426138*x[1] + 0.1737437357735736*x[2] + 0.5038759342570451*x[3] + 0.658971937352602*x[4] + 0.4229154972224074*x[5] + 0.8988055705389945*x[6] + 0.12696521992268772*x[7] + 0.2696889051029834*x[8] + 0.921857501988341*x[9] + 0.9890427015464145*x[10] + 0.2577621470581394*x[11] + 0.19668542250538879*x[12] + 0.3681791519767599*x[13] + 0.6436590468883737*x[14] + 0.13769107754636567*x[15] + 0.39732983988583825*x[16] + 0.10859306965431526*x[17] + 0.4705560830287482*x[18] : +Inf : True 5 Declarations: x_index x obj не_меньше_index не_меньше
def print_solution(m): for v in m.component_data_objects(pyo.Var): if v.value and v.value > 0: print(str(v), v.value)
solver = pyo.SolverFactory('cbc') solver.solve(m).write() print_solution(m)
# ========================================================== # = Solver Results = # ========================================================== # ---------------------------------------------------------- # Problem Information # ---------------------------------------------------------- Problem: - Name: unknown Lower bound: 4.50148447 Upper bound: 4.50148447 Number of objectives: 1 Number of constraints: 12 Number of variables: 19 Number of binary variables: 19 Number of integer variables: 19 Number of nonzeros: 19 Sense: minimize # ---------------------------------------------------------- # Solver Information # ---------------------------------------------------------- Solver: - Status: ok User time: -1.0 System time: 0.04 Wallclock time: 0.04 Termination condition: optimal Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available. Statistics: Branch and bound: Number of bounded subproblems: 0 Number of created subproblems: 0 Black box: Number of iterations: 0 Error rc: 0 Time: 0.14116787910461426 # ---------------------------------------------------------- # Solution Information # ---------------------------------------------------------- Solution: - number of solutions: 0 number of solutions displayed: 0 x[0] 1.0 x[2] 1.0 x[3] 1.0 x[4] 1.0 x[5] 1.0 x[6] 1.0 x[9] 1.0 x[10] 1.0 x[12] 1.0 x[13] 1.0 x[14] 1.0 x[18] 1.0